class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        int ret = dp[0] = nums[0]; 
        for(int i = 1; i < n; ++i)
        {
            dp[i] = max(nums[i], dp[i-1] + nums[i]);
            ret = max(ret, dp[i]);
        }
        return ret;
        // int ret = nums[0]; // 直接在原数组操作的dp
        // for (int i = 1; i < nums.size(); i++) 
        // {
        //     nums[i] += max(nums[i - 1], 0);
        //     ret = max(ret, nums[i]);
        // }
        // return ret;
    }
};